package pro.softzhang.algo.lc2300;

import com.alibaba.fastjson.JSON;
import pro.softzhang.algo.flag.knowledge.KBinarySearch;

import java.util.Arrays;

/**
 *
 */
public class LC2300_SuccessfulPairsOfSpellsAndPotions {
    public static void main(String[] args) {
        int[] spells = {5, 1, 3}, potions = {1, 2, 3, 4, 5};
        long success = 7;
        System.out.println(JSON.toJSONString(new Solution().successfulPairs(spells, potions, success)));
    }

    /**
     *
     */
    @KBinarySearch
    static
    class Solution {
        public int[] successfulPairs(int[] spells, int[] potions, long success) {
            Arrays.sort(potions);
            int n = spells.length, m = potions.length;
            int[] pairs = new int[n];
            for (int i = 0; i < n; i++) {
                long t = (success + spells[i] - 1) / spells[i] - 1;
                pairs[i] = m - binarySearch(potions, 0, m - 1, t);
            }
            return pairs;
        }

        public int binarySearch(int[] arr, int l, int h, long target) {
            int res = h + 1;
            while (l <= h) {
                int mid = l + (h - l) / 2;
                if (arr[mid] > target) {
                    res = mid;
                    h = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return res;
        }
    }
}
